package com.multimedia.scala.euler

import scala.collection.immutable.Queue
import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer
/**
A particular school offers cash rewards to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize.

During an n-day period a trinary string is formed for each child consisting of L's (late), O's (on time), and A's (absent).

Although there are eighty-one trinary strings for a 4-day period that can be formed, exactly forty-three strings would lead to a prize:

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO

How many "prize" strings exist over a 30-day period?
 */
object Asd191 {

    def main(args : Array[String]) : Unit = {
        (5 to 30).foreach(x=>  {
          //var count = Builder.count(x)
          
          //println(x+" "+count+"="+2*Builder.count(x-1)+"-"+Builder.countAA(x-1)+"+"+Builder.countAO(x-1))
          println(x+" "+Builder.countCached(x))
        })
        //println(Late()::Late()::OnTime()::Nil)
    }

	abstract case class Day
	case class Late extends Day
	case class OnTime extends Day
	case class Absent extends Day

	object Builder {
    	var cacheAO = ListBuffer[Int](2, 4, 7, 13, 24, 44)
    	var cache = ListBuffer[Int](3, 8, 19, 43, 94, 200)
	  
	    def countAO(size: Int = 30, last2: List[Day] = List[Day]()) : Int = {
            def canAbsent = last2.size<2||last2(0)!=Absent()||last2(1)!=Absent()
            def replaceLast(first: Day): List[Day] = {
              if (last2.length==0) return first::Nil
              else if (last2.length==1) return first::last2
              else return first::last2.dropRight(1)
            }

            if (cacheAO.size>size-1&&last2.isEmpty) return cacheAO(size-1)
	        if (size==1){
	            //println(last2.reverse, 1 + (if (wasLate) 0 else 1) + (if (canAbsent) 1 else 0))
	            return if (canAbsent) 2 else 1
	        }
            var rez = 0
            rez += countAO(size-1, replaceLast(OnTime()))
            if (canAbsent) rez += countAO(size-1, replaceLast(Absent()))

            if (cacheAO.size<size&&last2.isEmpty)cacheAO += rez
            return rez
	    }

    	def countAA(size: Int = 30) = count(size-3)+countAO(size-3)
    	
    	def countCached(size: Int = 30): Int = {
            if (cache.size>size-1) return cache(size-1)
    	    var rez = 2*Builder.count(size-1)-Builder.countAA(size-1)+Builder.countAO(size-1)
            if (cache.size<size)cache += rez
            return rez
    	}

        def count(size: Int = 30, last2: List[Day] = List[Day](), wasLate: Boolean = false): Int = {
            def canAbsent = last2.size<2||last2(0)!=Absent()||last2(1)!=Absent()
            def replaceLast(first: Day): List[Day] = {
              if (last2.length==0) return first::Nil
              else if (last2.length==1) return first::last2
              else return first::last2.dropRight(1)
            }

            if (cache.size>size-1&&last2.isEmpty) return cache(size-1)
	        if (size==1){
	            //println(last2.reverse, 1 + (if (wasLate) 0 else 1) + (if (canAbsent) 1 else 0))
	            return 1 + (if (wasLate) 0 else 1) + (if (canAbsent) 1 else 0)
	        }
            var rez = 0
            rez += count(size-1, replaceLast(OnTime()), wasLate)
            if (canAbsent) rez += count(size-1, replaceLast(Absent()), wasLate)
            if (!wasLate) rez += count(size-1, replaceLast(Late()), true)

            if (cache.size<size&&last2.isEmpty)cache += rez
            return rez
        }
	}
}


